package algorithm.dp;

import java.util.Scanner;

/**
 * @author apple
 * @Classname DynamicProgramming3
 * @Description 动态规划 例题3
 * @Date 2020/4/27 10:13
 */
public class DynamicProgramming3 {

    /**
     * 在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），
     * 与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。
     *
     * @param weight  背包最大可装重量
     * @param count   物品数量
     * @param weights 物品对应重量
     * @param costs   物品对应价值
     **/
    public static int weightBag(int weight, int count, int[] weights, int[] costs) {
//        // 物品数量
//        System.out.println("输入物品数量");
//        int n = 3;
//        // 背包最大容量
//        System.out.println("输入背包最大容量");
//        int weight = 12;
//        // 每个物品的重量，这里前面的0是为了后面表示方便，即weights[1]表示为第一个物品的重量，下同
//        int weights[] = {0, 5, 3, 4, 2, 8};
//        // 每个物品的价值
//        int value[] = {0, 20, 10, 12, 14, 18};
        int dp[][] = new int[count + 1][weight + 1];

        dp[0][weight] = 0;

        for (int i = 1; i <= count; i++) {
            for (int j = 1; j <= weight; j++) {
                if (i > 0 && j >= weights[i]) {
                    // 状态转移方程
                    //   dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - weights[i]] + costs[i]) ? dp[i - 1][j] : dp[i - 1][j - weights[i]] + costs[i];
//                    dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - weights[i]] + costs[i]) ? dp[i - 1][j] : dp[i - 1][j - weights[i]] + costs[i];
                    if (dp[i - 1][j] > dp[i - 1][j - weights[i]] + costs[i]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j - weights[i]] + costs[i];
                    }
                }
            }
        }
        return dp[count][weight];
    }

    /**
     * 在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），
     * * 与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。
     * *
     * * @param bagWeight  背包最大可装重量
     * * @param count   物品数量
     * * @param weights 物品对应重量
     * * @param costs   物品对应价值
     **/
    public static int weightBag2(int bagWeight, int count, int[] weights, int[] costs) {
        /**物品加入背包的数组，items[i]=1 该编号物品加入，items[i]=0,该编号物品未加入**/
        int[] items = new int[count + 1];
        int tempCost = 0;
        /**初始化结果数组
         * 声明动态规划表.其中dp[i][j]对应于：当前有i个物品可选，并且当前背包的容量为j时，我们能得到的最大价值**/
        int dp[][] = new int[count + 1][bagWeight + 1];

        /**填动态规划表。当前有i个物品可选，并且当前背包的容量为j。
         *i为包里物品数量， j为背包剩余容量
         */
        for (int i = 0; i < count + 1; i++) {
            for (int j = 0; j < bagWeight + 1; j++) {
                if (i == 0 || j == 0) {
                    /**边界问题**/
                    dp[i][j] = 0;
                } else {
                    if (j < weights[i]) {
                        /**背包剩余容量小于当前物品重量时,该物品不计入背包内，该数组位置的值为上一个物品数量的值**/
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        /**背包剩余容量大于当前物品重量时，有两种选择:放入或不放入。
                         * 判断标准，所以在装与不装之间选择最优的一个，即dp(i,j)=max｛dp(i-1,j)，dp(i-1,j-weights(i))+costs(i)｝。**/
                        tempCost = dp[i][j];
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + costs[i]);
                        /**当背包内物品价值变化时，该物品加入背包**/
                        if (tempCost < dp[i][j]) {
                            items[i] = 1;
                        }
                    }
                }
            }
        }
        System.out.println("动态规划表如下：");
        for (int i = 0; i < count + 1; i++) {
            for (int j = 0; j < bagWeight + 1; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
        /** 有count个物品可选，且背包的容量为bagWeight的情况下，能装入背包的最大价值**/
        System.out.println("背包内最大的物品价值总和为：" + dp[count][bagWeight]);
        /**放入哪些物品**/
        System.out.print("放入的物品编号: ");
        for (int i = 0; i < items.length; i++) {
            if (items[i] == 1) {
                System.out.print((i+1)+" ");
            }
        }
        System.out.println();

        /**返回结果集的最后一个元素**/
        return dp[count][bagWeight];
    }



    /**
     * 正整数分组
     * 将一堆正整数分为2组，要求2组的和相差最小。
     * 例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。
     **/
    public static void splitList() {
        /**输入数组元素的个数**/
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long sum = 0, max = 0;
        int[] nums = new int[n];
        /**输入数组元素**/
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
            sum += nums[i];
        }
        /**数组中所有元素的和的一半**/
        int[] dp = new int[(int) (sum / 2 + 1)];
        for (int i = 0; i < n; i++) {
            for (int j = (int) (sum / 2); j > 0; j--) {
                if (j >= nums[i]) {
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
        }
        for (int i = 1; i < sum / 2 + 1; i++) {
            max = max > dp[i] ? max : dp[i];
        }
        System.out.println(Math.abs((sum - max) - max));
    }

    public static void main(String[] args) {
        System.out.println("正整数分组");
//        splitList();

        System.out.println("背包问题");
        /**背包容量**/
        int weight = 22;
        /**物品数量**/
        int count =5;
        /**物品对应的重量**/
        int[] weights = {0, 5, 3, 4,6,8};
        /**物品对应的价值**/
        int[] costs = {0, 20, 10, 12,16,18};

        System.out.println(weightBag2(weight, count, weights, costs));
    }
}
